LC2008. 出租车的最大盈利

1. 题目

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开 到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [startᵢ, endᵢ, tipᵢ] 表示 第 i 位乘客需要从地点 startᵢ 前往 endᵢ ，愿意支付 tipᵢ 元的小费。

每一位 你选择接单的乘客 i ，你可以 盈利 endᵢ - startᵢ + tipᵢ 元。你同时 最多 只能接 一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

注意： 你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

示例 1：

输入：n = 5, rides = [[2,5,4],[1,5,1]]
输出：7
解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。

示例 2：

输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
输出：20
解释：我们可以接以下乘客的订单：
- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。

提示：

• 1 <= n <= 10⁵
• 1 <= rides.length <= 3 * 10⁴
• rides[i].length == 3
• 1 <= startᵢ < endᵢ <= n
• 1 <= tipᵢ <= 10⁵

2. 思路

• 利用 f[i] 维护状态，其中，i 表示，从地点 0 到 地点 i， 可以获得的最大收益。显然，最终答案为 f[n]
• 官方解答的思路比较直观，利用哈希表存储 rides 信息，其中，key 为每次到站的位置，即 ride[1], value 为 二维数组 ride（包括起始位置，到站位置和小费）。

// f[ride[0]] 为该 ride 在起始位置获得的收益
// ride[2] + ride[1] - ride[0] 为本次ride 获取的利益
f[i] = maxx(f[ride[0]] + (ride[2] + ride[1] - ride[0]), f[i])

---

• 为什么不担心是否载客的取舍？不利用二维 dp 来维护状态机？如下图所示

3. 代码

// Created by Albert's server at 2023/12/20 13:26
// leetgo: dev
// https://leetcode.cn/problems/maximum-earnings-from-taxi/

package main

import (
	"bufio"
	"fmt"
	"os"

	. "github.com/j178/leetgo/testutils/go"
)

// @lc code=begin
// f[i] = m, end with i, max profit is m
// f[i] = f[i-1]
// f[i] = f[k] + profit[k] ==> k can get max profit
func maxTaxiEarnings(n int, rides [][]int) (ans int64) {
	rec := make(map[int][][]int)

	for _, ride := range rides {
		rec[ride[1]] = append(rec[ride[1]], ride)
	}

	f := make([]int, n+1)
	f[0] = 0
	for i := 1; i <= n; i++ {
		f[i] = f[i-1]
		for _, ride := range rec[i] {
			f[i] = maxx(f[i], f[ride[0]]+ride[2]+ride[1]-ride[0])
		}
	}

	return int64(maxx(f...))
}

func maxx(nums ...int) int {
	res := nums[0]
	for _, v := range nums {
		if res < v {
			res = v
		}
	}

	return res
}

// @lc code=end

func main() {
	file, err := os.Open("./testcases.txt")
	if err != nil {
		fmt.Println("Error", err)
		return
	}

	in := bufio.NewReader(file)
	defer file.Close()

	ReadLine(in)
	n := Deserialize[int](ReadLine(in))
	rides := Deserialize[[][]int](ReadLine(in))
	ans := maxTaxiEarnings(n, rides)

	fmt.Println("\noutput:", Serialize(ans))
}